题解 P2414 【[NOI2011]阿狸的打字机】

发表于 | 更新于

$Description$

打字机上只有$28$个按键，分别印有$26$个小写英文字母和$’B’$、$’P’$两个字母。这个打字机是这样工作的：

输入小写字母，打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

按一下印有$’B’$的按键，打字机凹槽中最后一个字母会消失。

按一下印有$’P’$的按键，打字机会在纸上打印出凹槽中现有的所有字母并换行，但凹槽中的字母不会消失。 例如，阿狸输入$aPaPBbP$，纸上被打印的字符如下：$a aa ab$我们把纸上打印出来的字符串从$1$开始顺序编号，一直到$n$。打字机有一个非常有趣的功能，在打字机中暗藏一个带数字的小键盘，在小键盘上输入两个数$(x,y)($其中$1\leqslant x,y\leqslant n)$，打字机会显示第$x$个打印的字符串在第$y$个打印的字符串中出现了多少次。

$Solution:$

先无脑搭出一只$AC$自动机再说，然后再考虑各档分的做法

$40$

给每个串的结束位置都标记一下，给$AC$自动机中的每个节点记录一个父亲节点，然后对于每个串的结束位置都暴力往上跳，计算有几个被标记过的节点即可

$70(1)$

这样对于每一个询问都要暴力往上跳

如果对于某个串有重复的多次询问

那么就会多很多次没有任何意义的计算

所以，可以离线把所有询问都按照$y$排序

$y$相同的询问将从$y$向上跳碰到的标记记录下来，最后一起统计

$70(2)$

原来是$y$的某个节点往上跳能不能到达$x$

现在反过来：

$x$往下跳能够到达几个$y$的节点

如果把$y$这个字符串所有的节点全部打上一个$1$的标记

那么，每次就变成了求$x$结束位置的子树和

而一个点的子树在$dfs$序上一定是连续的一段

单点修改，区间查询，考虑用树状数组打标记

$100$

每次把串插入进树状数组会导致很多的串会有重复

考虑对$Trie$进行$dfs$

对于每个节点访问到的时候对它的$dfs$序打一个$+1$,结束的时候对它的$dfs$序打一个$-1$

每次访问到一个结束节点的时候，一定是有且仅有这个结束节点对应的串的所有节点被打了标记，这样就可以直接回答这个串作为$y$的所有询问了

$Code$

$40$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 500007
using namespace std;
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
char s[N];
int tot,K,ch[N][26],fail[N],fa[N],w[N],ed[N];
void build_fail(){
    queue<int>q;
    for (int i=0;i<26;++i)if (ch[0][i])q.push(ch[0][i]);
    while (!q.empty()){
        int now=q.front();q.pop();
        for (int i=0;i<26;++i)
            if (ch[now][i])
                fail[ch[now][i]]=ch[fail[now]][i],q.push(ch[now][i]);
            else ch[now][i]=ch[fail[now]][i];
    }
}
int query(int x,int y){
    int res=0;
    for (int now=ed[y];now;now=fa[now])
        for (int t=now;t;t=fail[t])
            if (w[t]==x){
                ++res;break;
            }
    return res;
}
signed main(){
    scanf("%s",s);int len=strlen(s);
    int now=0;
    for (int i=0;i<len;++i){
        if (s[i]=='B'){
            now=fa[now];
        }else if (s[i]=='P'){
            ed[++K]=now;w[now]=K;
        }else{
            int v=s[i]-'a';
            if (!ch[now][v])ch[now][v]=++tot,fa[tot]=now;
            now=ch[now][v];
        }
    }
    build_fail();
    int n=read();
    for (int i=1;i<=n;++i){
        int x=read(),y=read();
        printf("%d\n",query(x,y));
    }
    return 0;
}

$70(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 500007
using namespace std;
struct node{
    int x,y,num;
}q[N];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
char s[N];
int cnt[N],tot,K,ch[N][26],ans[N],fail[N],fa[N],w[N],ed[N];
void build_fail(){
    queue<int>q;
    for (int i=0;i<26;++i)if (ch[0][i])q.push(ch[0][i]);
    while (!q.empty()){
        int now=q.front();q.pop();
        for (int i=0;i<26;++i)
            if (ch[now][i])
                fail[ch[now][i]]=ch[fail[now]][i],q.push(ch[now][i]);
            else ch[now][i]=ch[fail[now]][i];
    }
}
int query(int y){
    int res=0;
    for (int now=ed[y];now;now=fa[now])
        for (int t=now;t;t=fail[t]){
            ++cnt[w[t]];
        }
    return res;
}
inline bool cmp(node a,node b){
    return a.y<b.y;
}
signed main(){
    scanf("%s",s);int len=strlen(s);
    int now=0;
    for (int i=0;i<len;++i){
        if (s[i]=='B'){
            now=fa[now];
        }else if (s[i]=='P'){
            ed[++K]=now;w[now]=K;
        }else{
            int v=s[i]-'a';
            if (!ch[now][v])ch[now][v]=++tot,fa[tot]=now;
            now=ch[now][v];
        }
    }
    build_fail();
    int n=read();
    for (int i=1;i<=n;++i)q[i].x=read(),q[i].y=read(),q[i].num=i;
    sort(q+1,q+1+n,cmp);
    for (int i=1,j=1;i<=n;i=j){
        query(q[i].y);
        while (q[i].y==q[j].y)ans[q[j].num]=cnt[q[j].x],++j;
        memset(cnt,0,sizeof(cnt));
    }    
    for (int i=1;i<=n;++i)printf("%d\n",ans[i]);
    return 0;
}

$70(2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 500007
using namespace std;
struct node{
    int x,y,num;
}q[N];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
char s[N];
int cnt[N],tot,K,ch[N][26],ans[N],fail[N],fa[N],w[N],ed[N];
void build_fail(){
    queue<int>q;
    for (int i=0;i<26;++i)if (ch[0][i])q.push(ch[0][i]);
    while (!q.empty()){
        int now=q.front();q.pop();
        for (int i=0;i<26;++i)
            if (ch[now][i])
                fail[ch[now][i]]=ch[fail[now]][i],q.push(ch[now][i]);
            else ch[now][i]=ch[fail[now]][i];
    }
}
int query(int y){
    int res=0;
    for (int now=ed[y];now;now=fa[now])
        for (int t=now;t;t=fail[t]){
            ++cnt[w[t]];
        }
    return res;
}
inline bool cmp(node a,node b){
    return a.y<b.y;
}
signed main(){
    scanf("%s",s);int len=strlen(s);
    int now=0;
    for (int i=0;i<len;++i){
        if (s[i]=='B'){
            now=fa[now];
        }else if (s[i]=='P'){
            ed[++K]=now;w[now]=K;
        }else{
            int v=s[i]-'a';
            if (!ch[now][v])ch[now][v]=++tot,fa[tot]=now;
            now=ch[now][v];
        }
    }
    build_fail();
    int n=read();
    for (int i=1;i<=n;++i)q[i].x=read(),q[i].y=read(),q[i].num=i;
    sort(q+1,q+1+n,cmp);
    for (int i=1,j=1;i<=n;i=j){
        query(q[i].y);
        while (q[i].y==q[j].y)ans[q[j].num]=cnt[q[j].x],++j;
        memset(cnt,0,sizeof(cnt));
    }    
    for (int i=1;i<=n;++i)printf("%d\n",ans[i]);
    return 0;
}

$100$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 500007
using namespace std;
struct edge{
    int to,next;
}e[N];
struct node{
    int x,y,num;
}q[N];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
char s[N];
int ql[N],qr[N],cc[N][26],ttt,head[N],dfn[N],low[N],dfsnum,c[100007],cnt[N],tot,K,ch[N][26],ans[N],fail[N],fa[N],w[N],ed[N];
void add(int x,int d){for (;x<=dfsnum;x+=(x&(-x)))c[x]+=d;}
int sum(int x){int res=0;for (;x;x&=x-1)res+=c[x];return res;}
void build_fail(){
    queue<int>q;
    for (int i=0;i<26;++i)if (ch[0][i])q.push(ch[0][i]);
    while (!q.empty()){
        int now=q.front();q.pop();
        for (int i=0;i<26;++i)
            if (ch[now][i])
                fail[ch[now][i]]=ch[fail[now]][i],q.push(ch[now][i]);
            else ch[now][i]=ch[fail[now]][i];
    }
}
int query(int y){
    int res=0;
    for (int now=ed[y];now;now=fa[now])
        for (int t=now;t;t=fail[t]){
            ++cnt[w[t]];
        }
    return res;
}
void Dfs(int u){
    dfn[u]=++dfsnum;
    for (int i=head[u];i;i=e[i].next)Dfs(e[i].to);
    low[u]=dfsnum;
}
inline void Add(int u,int v){
    e[++ttt].to=v;
    e[ttt].next=head[u];
    head[u]=ttt;
}
inline bool cmp(node a,node b){
    return a.y<b.y;
}
void dfs(int u){
    add(dfn[u],1);
    if (w[u])
        for (int i=ql[w[u]];i<=qr[w[u]];++i)
            ans[q[i].num]=sum(low[ed[q[i].x]])-sum(dfn[ed[q[i].x]]-1);
    for (int i=0;i<26;++i)
        if (cc[u][i]){
            dfs(cc[u][i]);
        }
    add(dfn[u],-1);
}
signed main(){
    scanf("%s",s);int len=strlen(s);
    int now=0;
    for (int i=0;i<len;++i){
        if (s[i]=='B'){
            now=fa[now];
        }else if (s[i]=='P'){
            ed[++K]=now;w[now]=K;
        }else{
            int v=s[i]-'a';
            if (!ch[now][v])ch[now][v]=++tot,fa[tot]=now;
            now=ch[now][v];
        }
    }
    for (int i=0;i<=tot;++i)
        for (int j=0;j<26;++j)
            cc[i][j]=ch[i][j];
    build_fail();
    for (int i=1;i<=tot;++i)Add(fail[i],i);Dfs(0);
    int n=read();
    for (int i=1;i<=n;++i)q[i].x=read(),q[i].y=read(),q[i].num=i;
    sort(q+1,q+1+n,cmp);
    for (int i=1,j=1;i<=n;i=j){
        ql[q[i].y]=i;
        while (q[i].y==q[j].y)++j;
        qr[q[i].y]=j-1;
    }
    dfs(0);
    for (int i=1;i<=n;++i)printf("%d\n",ans[i]);
    return 0;
}